package com.example.algorithm.backtrcaking.backrewrite;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/25
 * 全排列2
 */
public class AllArrayTwo {

    List<List<Integer>> listList=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len=nums.length;
        Arrays.sort(nums);
        boolean []flag=new boolean[len];
        backTracking(len,nums,flag);
        return listList;
    }

    private void backTracking(int len, int[] nums,boolean[]flag) {

        if(list.size()==len)
        {
            listList.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<len;i++)
        {
            if(flag[i])
            {
                continue;
            }
            if(i>0&&nums[i]==nums[i-1]&&!flag[i-1]){
                continue;
            }
            flag[i]=true;
            list.add(nums[i]);
            backTracking(len, nums, flag);
            flag[i]=false;
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        AllArrayTwo allArrayTwo = new AllArrayTwo();
        int[]can={1,1,2};
        List<List<Integer>> list = allArrayTwo.permuteUnique(can);
        list.stream().forEach(System.out::println);
    }
}
